package com.wangzh.data.arithmetic.recursion;

import java.util.Arrays;

public class Test2 {

    private static int count=0;
    public static void main(String[] args) {

        int n=5;
        int[] cache = new int[n];
        Arrays.fill(cache,-1);
        System.out.println(f(n, cache));
        System.out.println(count);
    }
    //多路递归，可以根据记忆法优化  爬楼梯问题，兔子个数问题，斐波那契
    //斐波那契f(n) = f(n-1)+f(n+2)
    //  1   1   2   3   5   8
    public static int f(int n,int[] cache){
        count++;


        if (n==1){
            return 1;
        }
        if (n==2){
            return 1;
        }
        return f(n-1,cache)+f(n-2,cache);
    }
}
